<!DOCTYPE html>
<html>
  <head>
  <meta http-equiv="content-type" content="text/html; charset=utf-8">
  <meta content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0" name="viewport">
  <meta name="description" content="Jce-Eric&#39;s blog">
  <meta name="keyword" content="hexo-theme, vuejs">
  
    <link rel="shortcut icon" href="/blog/css/images/logo.png">
  
  <title>
    
      快速排序 | Jce Eric
    
  </title>
  <link href="//cdnjs.cloudflare.com/ajax/libs/font-awesome/4.7.0/css/font-awesome.min.css" rel="stylesheet">
  <link href="//cdnjs.cloudflare.com/ajax/libs/nprogress/0.2.0/nprogress.min.css" rel="stylesheet">
  <link href="//cdnjs.cloudflare.com/ajax/libs/highlight.js/9.12.0/styles/tomorrow.min.css" rel="stylesheet">
  <link rel="stylesheet" href="/blog/css/style.css">
  
    <link rel="stylesheet" href="/blog/css/plugins/gitment.css">
  
  <script src="//cdnjs.cloudflare.com/ajax/libs/jquery/3.2.1/jquery.min.js"></script>
  <script src="//cdnjs.cloudflare.com/ajax/libs/geopattern/1.2.3/js/geopattern.min.js"></script>
  <script src="//cdnjs.cloudflare.com/ajax/libs/nprogress/0.2.0/nprogress.min.js"></script>
  
    <script src="/blog/js/qrious.js"></script>
  
  
    <script src="/blog/js/gitment.js"></script>
  
  
  
    <!-- MathJax support START -->
    <script type="text/x-mathjax-config">
      MathJax.Hub.Config({
        tex2jax: {
          inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
          processEscapes: true,
          skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
        }
      });
    </script>

    <script type="text/x-mathjax-config">
      MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for (i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
        }
      });
    </script>
    <script type="text/javascript" src="//cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
    <!-- MathJax support END -->
  


</head>
<div class="wechat-share">
  <img src="/css/images/logo.png" />
</div>

  <body>
    <header class="header fixed-header">
  <div class="header-container">
    <a class="home-link" href="/blog/">
      <div class="logo"></div>
      <span>Jce Eric</span>
    </a>
    <ul class="right-list">
      
        <li class="list-item">
          
            <a href="/blog/" class="item-link">Home</a>
          
        </li>
      
        <li class="list-item">
          
            <a href="/blog/tags/" class="item-link">Tags</a>
          
        </li>
      
        <li class="list-item">
          
            <a href="/blog/archives/" class="item-link">Archives</a>
          
        </li>
      
        <li class="list-item">
          
            <a href="/blog/project/" class="item-link">Projects</a>
          
        </li>
      
        <li class="list-item">
          
            <a href="/blog/about/" class="item-link">About</a>
          
        </li>
      
    </ul>
    <div class="menu">
      <span class="icon-bar"></span>
      <span class="icon-bar"></span>
      <span class="icon-bar"></span>
    </div>
    <div class="menu-mask">
      <ul class="menu-list">
        
          <li class="menu-item">
            
              <a href="/blog/" class="menu-link">Home</a>
            
          </li>
        
          <li class="menu-item">
            
              <a href="/blog/tags/" class="menu-link">Tags</a>
            
          </li>
        
          <li class="menu-item">
            
              <a href="/blog/archives/" class="menu-link">Archives</a>
            
          </li>
        
          <li class="menu-item">
            
              <a href="/blog/project/" class="menu-link">Projects</a>
            
          </li>
        
          <li class="menu-item">
            
              <a href="/blog/about/" class="menu-link">About</a>
            
          </li>
        
      </ul>
    </div>
  </div>
</header>

    <div id="article-banner">
  <h2>快速排序</h2>
  <p class="post-date">2019-09-19</p>
  <div class="arrow-down">
    <a href="javascript:;"></a>
  </div>
</div>
<main class="app-body flex-box">
  <!-- Article START -->
  <article class="post-article">
    <section class="markdown-content"><h2 id="基本思想"><a href="#基本思想" class="headerlink" title="基本思想"></a>基本思想</h2><blockquote>
<p>快速排序采用分治的思想。</p>
</blockquote>
<p>对于一个数组arr，假定要使它变成升序的数组，我们选取第0个元素作为基准数，根据这个基准数，把数组分为两部分，一部分是所有元素都比基准数大的，另外一部分是所有元素都比基准数小或相等的。对于这两部分，我们把其看成一个独立的数组，再按照上述流程进行递归处理即可。<br><strong>那怎么把数组根据基准数进行拆分呢？</strong><br>我们定义两个变量i，j，分别指向数组的头部和尾部。j先从右到左进行扫描，找到比基准数小或相等的元素就停下来，i从左到右进行扫描，找到比基准数大的元素就停下来，此时把i和j指向的元素互换，j和i继续扫描，直到j和i相遇，再把i（也是j）指向的元素和基准数进行交换，这样，数组就分为了<code>[start, i]</code> 和 <code>[i + 1, end]</code> 两个部分。</p>
<h2 id="递归实现"><a href="#递归实现" class="headerlink" title="递归实现"></a>递归实现</h2><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">quickSort</span><span class="params">(<span class="keyword">int</span>[] arr)</span></span>&#123;</span><br><span class="line">    quickSort(arr, <span class="number">0</span>, arr.length -<span class="number">1</span>);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">quickSort</span><span class="params">(<span class="keyword">int</span>[] arr, <span class="keyword">int</span> start, <span class="keyword">int</span> end)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(end &gt;= start)&#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> base = arr[start];</span><br><span class="line">    <span class="keyword">int</span> i = start, j = end;</span><br><span class="line">    <span class="keyword">while</span>(i &lt; j)&#123;</span><br><span class="line">        <span class="keyword">while</span>(i &lt; j &amp;&amp; arr[j] &gt; base)&#123;</span><br><span class="line">            j--;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">while</span>(i &lt; j &amp;&amp; arr[i] &lt;= base)&#123;</span><br><span class="line">            i++;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span>(i &lt; j)&#123;</span><br><span class="line">            swap(arr, i, j);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    arr[start] = arr[i];</span><br><span class="line">    arr[i] = base;</span><br><span class="line">    quickSort(arr, start, i - <span class="number">1</span>);</span><br><span class="line">    quickSort(arr, i + <span class="number">1</span>, end);</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">swap</span><span class="params">(<span class="keyword">int</span>[] arr, <span class="keyword">int</span> x, <span class="keyword">int</span> y)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> temp = arr[x];</span><br><span class="line">    arr[x] = arr[y];</span><br><span class="line">    arr[y] = temp;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<blockquote>
<p><strong>为什么要j先开始扫描呢？</strong><br>我们把第0个元素作为基准数。<br>对于数组arr = [10, 1, 2, 3, 20] 和 arr = [10, 1, 2, 3, 4]，若让i先开始，当i和j相遇时，i都会一直走到arr[4]，而j没有动过，还是初始值，此时我们无法判断arr[4]的值是比基准数大还是小，我们得额外进行判断。<br>对于数组arr = [1, 2, 3, 4, 10]，若让j先开始，当i和j相遇时，j会一直走到arr[0]，而i没有动过，还是初始值，但是arr[0]的值我们是知道的，就是基准数。</p>
<p><strong>总结：这其实是跟我们取基准数的方式有关的，当我们取最左边作为基准数时，就要从右边先开始，当我们取最右边作为基准数时，就要从左边先开始。</strong></p>
</blockquote>
<blockquote>
<p><strong>快速排序和归并排序</strong><br>把递归看成一颗二叉树，那么：<br>快速排序：下层递归的实现，依赖于上层递归的结果（只有父节点处理完成，才能处理完成子节点）<br>归并排序：上层递归的实现，依赖于下层递归的结构（只有子节点处理完成，才能处理完成父节点）</p>
</blockquote>
<h2 id="非递归实现"><a href="#非递归实现" class="headerlink" title="非递归实现"></a>非递归实现</h2><p>非递归的实现和递归实现大致上是差不多的，递归实现时，我们每次递归时，有参数start和end，就可以知道本次函数调用需要处理哪个范围内的元素。而非递归实现时，我们就需要找一个结构来记录当前循环处理的范围，这里使用栈和队列都是可行的，因为上层递归的操作不依赖于下层递归的结果。但是下层递归的操作依赖于上层递归的结果，所以我们只要每次把上层的操作先处理完，然后再把下层该处理的范围放入到栈或队列中，也就是说，每次从栈中取出当前该处理的范围，处理完后，再把下层该处理的范围入栈即可。</p>
<p>我们先定义一个类Iterm，用于记录当前需要处理的范围，即存储start和end。<br><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Iterm</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> start;</span><br><span class="line">    <span class="keyword">int</span> end;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">Iterm</span><span class="params">(<span class="keyword">int</span> start, <span class="keyword">int</span> end)</span></span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.start = start;</span><br><span class="line">        <span class="keyword">this</span>.end = end;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>具体实现：<br><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">quickSort_Iterator</span><span class="params">(<span class="keyword">int</span>[] arr)</span></span>&#123;</span><br><span class="line">    Stack&lt;Iterm&gt; stack = <span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">    Iterm root = <span class="keyword">new</span> Iterm(<span class="number">0</span>, arr.length - <span class="number">1</span>);</span><br><span class="line">    stack.push(root);</span><br><span class="line">    <span class="keyword">while</span>(!stack.isEmpty())&#123;</span><br><span class="line">        Iterm iterm = stack.pop();</span><br><span class="line">        <span class="keyword">int</span> start = iterm.start;</span><br><span class="line">        <span class="keyword">int</span> end = iterm.end;</span><br><span class="line">        <span class="keyword">if</span>(end - start &lt;= <span class="number">0</span>)&#123;</span><br><span class="line">            <span class="keyword">continue</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">int</span> base = arr[start];</span><br><span class="line">        <span class="keyword">int</span> i = start, j = end;</span><br><span class="line">        <span class="keyword">while</span>(i &lt; j)&#123;</span><br><span class="line">            <span class="keyword">while</span>(i &lt; j &amp;&amp; arr[j] &gt; base)&#123;</span><br><span class="line">                j--;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">while</span>(i &lt; j &amp;&amp; arr[i] &lt;= base)&#123;</span><br><span class="line">                i++;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span>(i &lt; j)&#123;</span><br><span class="line">                swap(arr, i, j);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        swap(arr, i, start);</span><br><span class="line">        Iterm firstPart = <span class="keyword">new</span> Iterm(start, i - <span class="number">1</span>);</span><br><span class="line">        Iterm secondPart = <span class="keyword">new</span> Iterm(i + <span class="number">1</span>, end);</span><br><span class="line">        stack.push(firstPart);</span><br><span class="line">        stack.push(secondPart);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h2 id="三路快排"><a href="#三路快排" class="headerlink" title="三路快排"></a>三路快排</h2><p>当数组中的相同元素较多时，使用普通快排，我们把数组分为两部分。<br><code>[ &lt;= base, &gt; base ]</code></p>
<p>我们发现数组中相同元素需要多次递归调用，大大影响排序的性能。如果我们能把数组分为三部分。<br><code>[ &lt; base, == base, &gt; base]</code></p>
<p>这样，在一次递归调用中，就能把相同元素都放在一起，后续的递归调用只需要处理<code>[ &lt; base ]</code>和 <code>[ &gt; base ]</code>这两部分，和base相等的元素无需参与后续的递归，速度自然大大提升。</p>
<p>若是想直接把数组分成3个部分，我们会发现，当我们找到等于base的元素要把其放在中间时，应该放在何处呢，因为此时还在排序中，我们并不知道 <code>[ &lt; base]</code>这部分有多大，这很难实现。我们可以先把数组分以下格式。<br><img src="/blog/blog/2019/09/19/quickSort/1.jpg" alt=""><br>i和j的定义同普通快排一致，j在移动中，把遇到的等于base的元素放在m指向的位置，而i在移动中，把遇到的等于base的元素放在n指向的位置。当i和j相遇时，数组被分为：<br><img src="/blog/blog/2019/09/19/quickSort/2.jpg" alt=""><br>然后把两边的<code>[ == base ]</code>移动到中间<br><img src="/blog/blog/2019/09/19/quickSort/3.jpg" alt=""><br>然后递归的处理的<code>[ &lt; base ]</code>和 <code>[ &gt; base ]</code>即可</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">quickSort3</span><span class="params">(<span class="keyword">int</span>[] arr)</span></span>&#123;</span><br><span class="line">    quickSort3(arr, <span class="number">0</span>, arr.length - <span class="number">1</span>);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">quickSort3</span><span class="params">(<span class="keyword">int</span>[] arr, <span class="keyword">int</span> start, <span class="keyword">int</span> end)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(end &lt;= start)&#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> i = start, n = start, j = end, m = end;</span><br><span class="line">    <span class="keyword">int</span> base = arr[start];</span><br><span class="line">    <span class="keyword">while</span>(i &lt; j)&#123;</span><br><span class="line">        <span class="keyword">while</span>(i &lt; j &amp;&amp; arr[j] &gt;= base)&#123;</span><br><span class="line">            <span class="keyword">if</span>(arr[j] == base)&#123;</span><br><span class="line">                swap(arr, j, m);</span><br><span class="line">                m--;</span><br><span class="line">            &#125;</span><br><span class="line">            j--;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">while</span>(i &lt; j &amp;&amp; arr[i] &lt;= base)&#123;</span><br><span class="line">            <span class="keyword">if</span>(arr[i] == base)&#123;</span><br><span class="line">                swap(arr, i, n);</span><br><span class="line">                n++;</span><br><span class="line">            &#125;</span><br><span class="line">            i++;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span>(i &lt; j)&#123;</span><br><span class="line">            swap(arr, i, j);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">/*move equals to center*/</span></span><br><span class="line">    n--;</span><br><span class="line">    m++;</span><br><span class="line">    j++;</span><br><span class="line">    <span class="keyword">while</span>(n &gt;= start)&#123;</span><br><span class="line">        swap(arr, n--, i--);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(m &lt;= end)&#123;</span><br><span class="line">        swap(arr, m++, j++);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">/*iterator*/</span></span><br><span class="line">    quickSort3(arr, start,i);</span><br><span class="line">    quickSort3(arr, j, end);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
</section>
    <!-- Tags START -->
    
      <div class="tags">
        <span>Tags:</span>
        
  <a href="/blog/blog/tags#数据结构与算法" >
    <span class="tag-code">数据结构与算法</span>
  </a>

      </div>
    
    <!-- Tags END -->
    <!-- NAV START -->
    
  <div class="nav-container">
    <!-- reverse left and right to put prev and next in a more logic postition -->
    
      <a class="nav-left" href="/blog/2019/08/31/traversalTree/">
        <span class="nav-arrow">← </span>
        
          二叉树的遍历
        
      </a>
    
    
      <a class="nav-right" href="/blog/2019/10/01/前中后缀表达式/">
        
          前、中、后缀表达式
        
        <span class="nav-arrow"> →</span>
      </a>
    
  </div>

    <!-- NAV END -->
    <!-- 打赏 START -->
    
    <!-- 打赏 END -->
    <!-- 二维码 START -->
    
      <div class="qrcode">
        <canvas id="share-qrcode"></canvas>
        <p class="notice">扫描二维码，分享此文章</p>
      </div>
    
    <!-- 二维码 END -->
    
      <!-- Gitment START -->
      <div id="comments"></div>
      <!-- Gitment END -->
    
  </article>
  <!-- Article END -->
  <!-- Catalog START -->
  
    <aside class="catalog-container">
  <div class="toc-main">
    <strong class="toc-title">Catalog</strong>
    
      <ol class="toc-nav"><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#基本思想"><span class="toc-nav-text">基本思想</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#递归实现"><span class="toc-nav-text">递归实现</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#非递归实现"><span class="toc-nav-text">非递归实现</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#三路快排"><span class="toc-nav-text">三路快排</span></a></li></ol>
    
  </div>
</aside>
  
  <!-- Catalog END -->
</main>

<script>
  (function () {
    var url = 'https://shachunleng.gitee.io/blog/2019/09/19/quickSort/';
    var banner = ''
    if (banner !== '' && banner !== 'undefined' && banner !== 'null') {
      $('#article-banner').css({
        'background-image': 'url(' + banner + ')'
      })
    } else {
      $('#article-banner').geopattern(url)
    }
    $('.header').removeClass('fixed-header')

    // error image
    $(".markdown-content img").on('error', function() {
      $(this).attr('src', 'http://file.muyutech.com/error-img.png')
      $(this).css({
        'cursor': 'default'
      })
    })

    // zoom image
    $(".markdown-content img").on('click', function() {
      var src = $(this).attr('src')
      if (src !== 'http://file.muyutech.com/error-img.png') {
        var imageW = $(this).width()
        var imageH = $(this).height()

        var zoom = ($(window).width() * 0.95 / imageW).toFixed(2)
        zoom = zoom < 1 ? 1 : zoom
        zoom = zoom > 2 ? 2 : zoom
        var transY = (($(window).height() - imageH) / 2).toFixed(2)

        $('body').append('<div class="image-view-wrap"><div class="image-view-inner"><img src="'+ src +'" /></div></div>')
        $('.image-view-wrap').addClass('wrap-active')
        $('.image-view-wrap img').css({
          'width': `${imageW}`,
          'transform': `translate3d(0, ${transY}px, 0) scale3d(${zoom}, ${zoom}, 1)`
        })
        $('html').css('overflow', 'hidden')

        $('.image-view-wrap').on('click', function() {
          $(this).remove()
          $('html').attr('style', '')
        })
      }
    })
  })();
</script>


  <script>
    var qr = new QRious({
      element: document.getElementById('share-qrcode'),
      value: document.location.href
    });
  </script>



  <script>
    var gitmentConfig = "Jce-Eric";
    if (gitmentConfig !== 'undefined') {
      var gitment = new Gitment({
        id: "快速排序",
        owner: "Jce-Eric",
        repo: "Jce-Eric.github.io",
        oauth: {
          client_id: "52af927fe48e6c1d9f7e",
          client_secret: "a7dc0d1a1a99003ca896eb1eeb7660967499d91e"
        },
        theme: {
          render(state, instance) {
            const container = document.createElement('div')
            container.lang = "en-US"
            container.className = 'gitment-container gitment-root-container'
            container.appendChild(instance.renderHeader(state, instance))
            container.appendChild(instance.renderEditor(state, instance))
            container.appendChild(instance.renderComments(state, instance))
            container.appendChild(instance.renderFooter(state, instance))
            return container;
          }
        }
      })
      gitment.render(document.getElementById('comments'))
    }
  </script>




    <div class="scroll-top">
  <span class="arrow-icon"></span>
</div>
    <footer class="app-footer">
  <p class="copyright">
    &copy; 2021 | Proudly powered by <a href="https://hexo.io" target="_blank">Hexo</a>
    <br>
    Theme by <a href="https://github.com/yanm1ng">yanm1ng</a>
  </p>
</footer>

<script>
  function async(u, c) {
    var d = document, t = 'script',
      o = d.createElement(t),
      s = d.getElementsByTagName(t)[0];
    o.src = u;
    if (c) { o.addEventListener('load', function (e) { c(null, e); }, false); }
    s.parentNode.insertBefore(o, s);
  }
</script>
<script>
  async("//cdnjs.cloudflare.com/ajax/libs/fastclick/1.0.6/fastclick.min.js", function(){
    FastClick.attach(document.body);
  })
</script>

<script>
  var hasLine = 'false';
  async("//cdnjs.cloudflare.com/ajax/libs/highlight.js/9.12.0/highlight.min.js", function(){
    $('figure pre').each(function(i, block) {
      var figure = $(this).parents('figure');
      if (hasLine === 'false') {
        figure.find('.gutter').hide();
      }
      var lang = figure.attr('class').split(' ')[1] || 'code';
      var codeHtml = $(this).html();
      var codeTag = document.createElement('code');
      codeTag.className = lang;
      codeTag.innerHTML = codeHtml;
      $(this).attr('class', '').empty().html(codeTag);
      figure.attr('data-lang', lang.toUpperCase());
      hljs.highlightBlock(block);
    });
  })
</script>
<!-- Baidu Tongji -->

<script src="/blog/js/script.js"></script>
  </body>
</html>